#include <iostream>
#include <vector>
#include <string>
bool KMP(std::string const& str1, std::string const& str2) {
	std::vector<int> next(str2.size(), 0);
	auto getNext = [&next, &str = str2]() {
		int j = 0;
		next[0] = 0;
		for (int i = 1; i < str.size(); ++i) {
			while (j > 0 && str[i] != str[j]) j = next[j - 1];
			if (str[i] == str[j]) ++j;
			next[i] = j;
		}
	};
	getNext();
	for (auto& v : next) {
		std::cout << v << " ";
	}
	std::cout << std::endl;
	int i = 0, j = 0;
	for (; i < str1.size() && j < str2.size(); ++i) {
		while (j > 0 && str1[i] != str2[j]) j = next[j - 1];
		if (str1[i] == str2[j]) ++j;
	}
	return (i == str1.size() && j == str2.size()) ? true : false;
}
int main(int argc, char** argv) {
	std::string str1 = "aaabaaaab";
	std::string str2 = "aaaab";
	std::cout << KMP(str1, str2) << std::endl;
	return 0;
}